Năm 581, Dương Kiên buộc Bắc Chu Tĩnh Đế phải thiện nhượng cho mình, trở thành Tùy Văn Đế. Vũ Văn Thuật được triều đình Tùy trao chức "hữu vệ đại tướng quân". Vào mùa đông năm 588, khi Tùy Văn Đế phái quân tiến công Nam triều Trần, Vũ Văn Thuật lại được làm 'hành quân tổng quản', suất ba vạn lính, vượt Trường Giang ở Lục Hợp. Sau khi quân của tướng Hàn Cầm Hổ (韓擒虎) và Hạ Nhược Bật (賀若弼) vượt Trường Giang và tiến đến Đan Dương, Vũ Văn Thuật tiến chiếm Thạch Đầu thành nhằm hỗ trợ. Sau khi Hạ Nhược Bật và Hàn Cầm Hổ chiếm được Kiến Khang và bắt hoàng đế Trần Thúc Bảo, các hạ thần của Trần là Tiêu Hiến (蕭瓛) và Tiêu Nham (蕭巖) chiếm cứ đất Đông Ngô, tập hợp binh sĩ cự thủ. Vũ Văn Thuật cùng với Lạc Tùng công Yên Vinh (燕榮) được phái đi tiến công Đông Ngô, kết quả đã đánh bại được Tiêu Hiến và buộc Tiêu Nham phải đầu hàng. Vĩnh Tân hầu Trần Quân Phạm (陳君范) chạy trốn và tập hợp binh sĩ, lập hàng rào ở đông thành Tấn Lăng, cắt đường của quân Tùy, lưu binh đánh Vũ Văn Thuật, song sau đó cũng phải đầu hàng. Để thưởng công cho Vũ Văn Thuật, Tùy Văn Đế trao chức "khai phủ" cho con của Thuật là Vũ Văn Hóa Cập, ban cho Thuật 3.000 tấm vải, trao chức tổng quản An châu (安州, nay gần tương ứng với Hiếu Cảm, Hồ Bắc).

Sau khi diệt được Trần, Tấn vương Dương Quảng cai quản Dương châu (揚州, nay gần tương ứng với Dương Châu, Giang Tô). Vũ Văn Thuật rất thân thiết với Dương Quảng, Dương Quảng vào năm 600 đã thượng tấu cho phụ hoàng xin trao cho Vũ Văn Thuật chức thứ sử tổng quản Thọ châu (壽州, nay gần tương ứng với Lục An, An Huy) để hai người được gần nhau hơn, Tùy Văn Đế đã chuẩn tấu.

Dương Quảng vốn có dã tâm thay thế vị trí thái tử của đại huynh Dương Dũng, vì thế đã thỉnh kế từ Vũ Văn Thuật. Vũ Văn Thuật đã đề xuất liên kết với Dương Tố, và hình thành mối quan hệ với Dương Tố thông qua đệ của Dương Tố là Dương Ước (楊約). Dương Quảng do đó đã ban thưởng nhiều vàng bạc châu báu cho Vũ Văn Thuật, và nhờ Vũ Văn Thuật đến kinh thành để gặp gỡ Dương Ước. Vũ Văn Thuật đã tặng cho Dương Ước một số đồ quý lấy được từ Trần, và sau đó cố ý không thắng khi hai người cùng đánh bạc. Sau khi trở nên thân thiết với Dương Ước, Vũ Văn Thuật đã tiết lộ với Dương Ước rằng Dương Quảng có ý muốn liên kết với Dương Tố, và thuyết phục Dương Ước rằng gia quyến của ông ta sẽ gặp nguy nếu đương kim Thái tử Dương Dũng kế vị. Dương Ước đã thuyết phục Dương Tố, Dương Tố nghe theo và thuyết phục Tùy Văn Đế cùng hoàng hậu Độc Cô Già La rằng nên phế truất Dương Dũng khỏi ngôi vị thái tử. Tùy Văn Đế và Độc Cô hoàng hậu chấp thuận, cho Dương Quảng thay thế vị trí hoàng thái tử của Dương Dũng. Dương Quảng đã trao chức 'tả vệ soái' cho Vũ Văn Thuật, hàng quan tứ phẩm; còn gả con mình là Nam Dương công chúa cho con của Vũ Văn Thuật là Vũ Văn Sĩ Cập (宇文士及).

Năm 604, trong lúc Tùy Văn Đế lâm bệnh, Vũ Văn Thuật là một trong các chỉ huy thị vệ mà Dương Quảng triệu đến để bảo vệ Nhân Thọ cung (仁壽宮, nay thuộc Bảo Kê, Thiểm Tây)- nơi Văn Đế dưỡng bệnh. Sau đó, Tùy Văn Đế qua đời, Dương Quảng kế vị, tức Tùy Dạng Đế, còn Dương Dũng bị Dương Quảng giết chết.